package com.celan.year2023.month01.day22;

import java.util.*;

public class Solution {
    private int m;
    private int[] val;
    private final Map<Integer, Integer> cache = new HashMap<>();

    public int maxHappyGroups(int batchSize, int[] groups) {
        m = batchSize;
        int ans = 0;
        int[] cnt = new int[m];
        /*
            先用贪心思路：x为m倍数的可以直接++ans，因为可以放在最前面；
            其次，二者相加可以整除m的进行配对，尽量减少会剩出来的情况；
            最后cnt记录的就是无法整除又无法配对的组的数量（%m后）
         */
        for (int x : groups) {
            x %= m;
            if (x == 0) ++ans; // 直接排在最前面
            else if (cnt[m - x] > 0) {
                --cnt[m - x]; // 配对
                ++ans;
            } else ++cnt[x];
        }
        //后续位运算加速看不懂了
        int mask = 0, n = 0;
        for (int c : cnt) if (c > 0) ++n;
        val = new int[n];
        for (int x = 1; x < m; ++x)
            if (cnt[x] > 0) {
                val[--n] = x; // val 越靠后的，在 mask 中的比特位越高
                mask = mask << 5 | cnt[x];
            }

        return ans + dfs(mask);
    }

    private int dfs(int mask) {
        if (cache.containsKey(mask)) return cache.get(mask);
        int res = 0, left = mask >> 20, msk = mask & ((1 << 20) - 1);
        for (int i = 0, j = 0; i < val.length; ++i, j += 5) // 枚举顾客
            if ((msk >> j & 31) > 0) // cnt[val[i]] > 0
                res = Math.max(res, (left == 0 ? 1 : 0) + dfs((left + val[i]) % m << 20 | msk - (1 << j)));
        cache.put(mask, res);
        return res;
    }

    //输入：answers = [1,1,2]
    //输出：5
    //解释：
    //两只回答了 "1" 的兔子可能有相同的颜色，设为红色。
    //之后回答了 "2" 的兔子不会是红色，否则他们的回答会相互矛盾。
    //设回答了 "2" 的兔子为蓝色。
    //此外，森林中还应有另外 2 只蓝色兔子的回答没有包含在数组中。
    //因此森林中兔子的最少数量是 5 只：3 只回答的和 2 只没有回答的。
    //输入：answers = [10,10,10]
    //输出：11
    public int numRabbits(int[] answers) {
        //排序，让相同数字排在一起
        Arrays.sort(answers);
        int res = 0;
        int idx = 0;
        while (idx < answers.length) {
            int answer = answers[idx];
            //先获取当前数字，记作一个颜色，当前颜色最多有answer+1个
            //向后遍历，遇到数字不同终止，并把这种颜色的数量加入res
            for (int i = 0; i <= answer; i++) {
                idx++;
                if (idx == answers.length) break;
                if (answer == answers[idx]) continue;
                else break;
            }
            res += answer + 1;
        }
        return res;
    }

    public String customSortString(String order, String s) {
        StringBuilder res = new StringBuilder();
        int[] dic = new int[26];
        for (int i = 0; i < s.length(); i++) {
            dic[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < order.length(); i++) {
            char c = order.charAt(i);
            while (dic[c - 'a'] > 0) {
                dic[c - 'a']--;
                res.append(c);
            }
        }
        for (int i = 0; i < 26; i++) {
            while (dic[i] > 0) {
                dic[i]--;
                res.append((char) (i + 'a'));
            }
        }
        return res.toString();
    }

    public String maskPII(String s) {
        //0为邮箱，1为手机号
        int type = resolveType(s);
        return type == 0 ? maskEmail(s) : maskPhone(s);
    }

    private String maskPhone(String s) {
        StringBuilder phone = new StringBuilder();
        StringBuilder res = new StringBuilder();
        //{'+', '-', '(', ')', ' '}
        for (char c : s.toCharArray()) {
            if (c == '+' || c == '-' || c == '(' || c == ')' || c == ' ') continue;
            phone.append(c);
        }
        int len = phone.length();
        String local = phone.substring(phone.length() - 4, phone.length());
        if (len - 10 == 0) {
            res.append("***-***-");
        }else if(len - 10 == 1){
            res.append("+*-***-***-");
        }else if(len - 10 == 2){
            res.append("+**-***-***-");
        }else if(len - 10 == 3){
            res.append("+***-***-***-");
        }
        res.append(local);
        return res.toString();
    }

    private String maskEmail(String s) {
        String[] split = s.split("@");
        String name = split[0];
        String ip = split[1];
        name = name.charAt(0) + "*****" + name.charAt(name.length() - 1);
        return toLow(name + "@" + ip);
    }

    private String toLow(String s) {
        StringBuilder res = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c >= 'A' && c <= 'Z') {
                c -= 'A' - 'a';
            }
            res.append(c);
        }
        return res.toString();
    }

    private int resolveType(String s) {
        for (char c : s.toCharArray()) {
            if (c == '@') return 0;
        }
        return 1;
    }

}
